class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # k个鸡蛋，扔t次 可以cover多少层楼（最多可以求解F=coverFloor(k,t)层楼的问题）
        memo = {}
        def coverFloor(k, t):
            if k==1: return t # 只有一个鸡蛋时，扔t次，只能从第一层开始逐层扔到t层
            if t==1 and k>0: return 1 # 只有1次机会时，只能扔在1层，cover N=1的情况
            if (k,t) in memo: return memo[(k,t)] # 备忘录
            s0 = coverFloor(k, t-1) # 扔完1次，没碎，接着向上面的楼层求解，还能cover多少层
            s1 = coverFloor(k-1, t-1) # 扔完1次，碎了，接着向下面面的楼层求解，还能cover多少层
            memo[(k,t)] = s0+s1+1 # +1表示当前扔的这一层
            return s0 + 1 + s1
        t=1
        while coverFloor(K, t)<N:
            t+=1
        return t   # 时间复杂度O(k*t)  由于memo的存在，不会重复计算

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def helper(k, n):
            if n == 1 and n > 0:
                return 1
            if k == 1: # 只有一个鸡蛋，只能在第一层一层扔，要k次
                return k
            s0 = helper(k, n-1) # 扔一次没碎，接着向上扔
            s1 = helper(k-1, n-1) # 鸡蛋碎了，楼层也少了
            return s0+s1+1
        n = 1
        while helper(K, n) < N:
            n += 1
        return n


if __name__ == "__main__":
    # for i in range(1,11):
    print( Solution().superEggDrop(2, 10))